package main.leetcode.clockin.September;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 637. 二叉树的层平均值
 *
 * <p>给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 *
 * <p>示例 1：输入： 3 / \ 9 20 / \ 15 7 输出：[3, 14.5, 11] 解释： 第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3,
 * 14.5, 11] 。
 *
 * <p>提示：节点值的范围在32位有符号整数范围内。
 */
public class day12 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.creCmpBTree(new int[] {3, 1, 5, 0, 2, 4, 6});
        //        TreeNode root = TreeNode.creCmpBTree(new int[] {2147483647, 2147483647,
        // 2147483647});
        System.out.println(new day12().averageOfLevels(root));
    }

    /** 迭代 */
    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<Double> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            long sum = 0;
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add((double) (sum / n));
        }
        return res;
    }

    //    /** 递归 */
    //    private List<Long> sum;
    //    private List<Integer> cnt;
    //
    //    public List<Double> averageOfLevels(TreeNode root) {
    //        if (root == null) {
    //            return new ArrayList<>();
    //        }
    //        sum = new ArrayList<>();
    //        cnt = new ArrayList<>();
    //        dfs(root, 0);
    //        List<Double> res = new ArrayList<>();
    //        int n = sum.size();
    //        for (int i = 0; i < n; i++) {
    //            res.add((double) sum.get(i) / cnt.get(i));
    //        }
    //        return res;
    //    }
    //
    //    private void dfs(TreeNode root, int level) {
    //        if (root == null) {
    //            return;
    //        }
    //        if (sum.size() - 1 < level) {
    //            sum.add(0L);
    //            cnt.add(0);
    //        }
    //        sum.set(level, sum.get(level) + root.val);
    //        cnt.set(level, cnt.get(level) + 1);
    //        dfs(root.left, level + 1);
    //        dfs(root.right, level + 1);
    //    }
}
